package com.ztom.offer.v2;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 包含 min 函数的栈
 * <p>
 * https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/
 *
 * @author ZhangTao
 */
public class Code28MinStack {

    /**
     * 辅助栈
     */
    class MinStack {
        private Deque<Integer> stack;
        private Deque<Integer> help;

        /** initialize your data structure here. */
        public MinStack() {
            this.stack = new LinkedList<>();
            this.help = new LinkedList<>();
        }

        public void push(int x) {
            if (help.isEmpty()) {
                help.offerLast(x);
            } else {
                help.offerLast(Math.min(help.peekLast(), x));
            }
            stack.offerLast(x);
        }

        public void pop() {
            if (!stack.isEmpty()) {
                stack.pollLast();
            }
            if (!help.isEmpty()) {
                help.pollLast();
            }
        }

        public int top() {
            return stack.isEmpty() ? -1 : stack.peekLast();
        }

        public int min() {
            return help.isEmpty() ? -1 : help.peekLast();
        }
    }

    /**
     * 链表自定义节点
     */
    class MinStack2 {

        class Node {
            private int val;
            private int min;
            private Node next;

            public Node(int val, int min, Node next) {
                this.val = val;
                this.min = min;
                this.next = next;
            }
        }

        private Node node;

        /** initialize your data structure here. */
        public MinStack2() {

        }

        public void push(int x) {
            if (node == null) {
                node = new Node(x, x, null);
            } else {
                // 生成新节点并将新节点作为父节点, 同时移动到新节点
                node = new Node(x, Math.min(node.min, x), node);
            }
        }

        public void pop() {
            node = node.next;
        }

        public int top() {
            return node.val;
        }

        public int min() {
            return node.min;
        }
    }
}
